import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 09
 * Time: 14:27
 */
//牛客 N皇后问题
public class Solution3 {
    char[][] arr;//是一个矩形
    int rowNum;
    int ret = 0;
    boolean[] checkCol;
    boolean[] checkDig1;
    boolean[] checkDig2;
    public int Nqueen (int n) {
        rowNum = n;
        checkCol = new boolean[n];
        checkDig1 = new boolean[2 * n];//注意是2*n(尽量取大一点)，因为col-row+arr.length的最大值(checkDig1数组下标的最大值)是2*n-1
        checkDig2 = new boolean[2 * n];//注意是2*n(尽量取大一点)，因为col+row的最大值(checkDig2数组下标的最大值)是2*n-2
        arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(arr[i], '.');
        }
        dfs(0);
        return ret;
    }
    public void dfs(int row) {
        if(row == rowNum) {//行越界的时候找到一种放皇后的方式
            ret++;
            return;
        }
        for (int col = 0; col < arr.length; col++) {//检验当前row(行)中的哪一col(列)可以放皇后
            if(checkCol[col] == false && checkDig1[col - row + arr.length] == false && checkDig2[col + row] == false) {//同一个主对角线的元素它们的下标col-row+arr.length的值一样，同一个副对角线的元素它们的下标col+row的值一样
                arr[row][col] = 'Q';//牛客这道题这一行可以不写，写了可提高可读性
                checkCol[col] = checkDig1[col - row + arr.length] = checkDig2[col + row] = true;
                dfs(row + 1);
                //有两种回溯，一种是走到尽头找到了一种放皇后的方式然后回溯，一种是在中途不符合条件剪枝回溯，两种回溯都要恢复现场
                arr[row][col] = '.';//牛客这道题这一行可以不写，写了可提高可读性
                checkCol[col] = checkDig1[col - row + arr.length] = checkDig2[col + row] = false;
            }
        }
    }
}
